Double Ratchet Algorithm

KDF chains

Resilience

The output keys appear random to an adversary without knowledege of the KDF keys. This is true even if the adversary can control the KDF inputs.

Forward security

Output keys from the past appear random to an adversary who learns the KDF key at some point in time.

Break-in recovery

Future output keys appear random to an adversary who learns the KDF key at some point in time, provided that future inputs have added sufficient entropy.

https://gyazo.com/a403db34581ae550b064809c766561ad

Symmetric-key rachet

message key

Every message sent or received is encrypted with a unique message key.

chain key

KDF keys for KDF chains.

The KDF inputs for the sending and receiving chains are constant, so these chains dont't provide break-in recovery.

Because message keys aren't used to derive any other keys, message keys may be stored without affecting the security of other message keys.

https://gyazo.com/5eda0cc8dada92d2e7bc1a6dd28ebbd2

Diffie-Hellman ratchet

Updates chain keys based on DH outputs to prevent an attacker from computing all future message keys by stealing one party's sending and receiving chain keys.

Each party generates a DH key pair which becomes thier current ratchet key pair and every message from either part begins with a header which contains the sender's current ratchet public key.

Messages sent by Alice advertise her new public key. Eventually, Bob will receive one of these messages and peform a second DH ratchet step.

https://gyazo.com/4da133d6a4b1ba563b3a508c13a099a9

Instead of taking the chain keys directly from DH outputs, these are used as KDF inputs to a root chain, and the KDF outputs from the root chain are used as sending and receiving chain keys.

Using a KDF chain improves resilience and break-in recovery.

https://gyazo.com/74b63e96cfe535e428f61fde040523b1

Double Ratchet

If Alice receives a response B1 from Bob, it will contain a new ratchet public key. Alice applies a DH ratchet step to derive new receiving and sending chain keys.Then she applies a symmetric-key ratchet step to the receiving chain to get the message key for the received message.

https://gyazo.com/7f41cd6d3adaff3197cb3de4529c7b2c

Out-of-order messages

Each message header includes:

N: the message's number in the sending chain

PN: the length(number of message keys) in the previous sending chain

https://gyazo.com/de4efd54abe771ec5b237f9c0b5db614